package org.example;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
//
//树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new LinkedList<>();
        if(root == null) return ret;
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        int c1 = 1;
        while(!queue.isEmpty()){
            int c2 = 0;
            List<Integer> lawyer = new LinkedList<>();//记录当前层的所有节点值
            for(int i = 0; i < c1; i++){
                Node node = queue.poll();//返回队头结点,并移除
                lawyer.add(node.val);
                //如果node的孩子节点不为空,将所有孩子节点放入队列
                if(!node.children.isEmpty()){
                    for (Node child : node.children) {
                        queue.add(child);
                        c2++;
                    }
                }
            }
            c1 = c2;
            //将当前层所有值加入ret
            ret.add(lawyer);
        }
        return ret;
    }
}
